package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         46,
		Discription: "无重复数组的排列组合",
		Level:       2,
		Labels: map[string]int{
			"递归":   1,
			"空间复用": 1,
			"去重":   1,
		},
	})
}

func Permute(nums []int) [][]int {
	res := make([][]int, 0)
	var travel func(int)
	travel = func(start int) {
		if start == len(nums) {
			res = append(res, append([]int(nil), nums...))
			return
		}

		//每选定一个数，将这个数的位置和数组的第一个数换，下一次递归从下一个数字开始
		for i := start; i < len(nums); i++ {
			nums[i], nums[start] = nums[start], nums[i]
			travel(start + 1)
			nums[i], nums[start] = nums[start], nums[i]
		}
	}

	travel(0)
	return res
}
